一、DCNN [2016]

《Diffusion-Convolutional Neural Networks》

1. 与结构化数据打交道是一种挑战。一方面，找到正确的方式来表达和利用数据中的结构可以改善预测性能；另一方面，找到这样的 representation 可能是困难的，而且在模型中添加结构会大大增加预测的复杂性。

   论文 《Diffusion-Convolutional Neural Networks》 的目标是为通用的结构化数据设计一个灵活的模型，在提高预测性能的同时避免复杂性的增加。为了实现这一目标，作者引入 "diffusion-convolution"操作，将卷积神经网络扩展到通用的图结构数据。简而言之，diffusion-convolution 操作不是像标准卷积操作那样在网格结构的输入中扫描一个 "正方形"，而是通过在图结构的输入中扫描每个节点的diffusion process 来建立一个 latent representation 。

   这个模型的动机是这样的：封装了 graph diffusion 的 representation 可以为预测提供一个比 graph 本身更好的 basis 。 graph diffusion 可以表示为一系列的矩阵幂次从而包含上下文信息，并且可以在多项式时间内计算，以及可以在 GPU 上有效实现。

   在论文 《Diffusion-Convolutional Neural Networks》 中，作者提出了 diffusion-convolutional neural network: DCNN ，并探讨了它们在图数据的各种分类任务中的表现。许多技术在分类任务中包括结构信息，如概率关系模型（probabilistic relational model）和核方法 （kernel method）。DCNN 提供了一种补充方法，在节点分类任务的预测性能上有了明显的改善。

   DCNN 的主要优势：

   • 准确性：在实验中，DCNN 在节点分类任务中的表现明显优于其他方法，在图分类任务中的表现与baseline方法相当。

   • 灵活性。DCNN提供了一种灵活的图数据表示方法，可以编码节点特征、边特征、以及单纯的结构信息，只需进行少量的预处理。DCNN 可用于图数据的各种分类任务，包括节点分类和图分类。

   • 速度快。DCNN 的预测可以表示为一系列的多项式时间的张量运算，并且该模型可以使用现有的库在GPU上有效地实现。

2. 相关工作：

   • 其它 graph-based 神经网络方法：其他研究者已经研究了如何将 CNN 从网格结构扩展到更普遍的图结构数据。

     • 《Spectral networks and locally connected networks on graphs》 提出了一种与层次聚类（hierarchical clustering）相联系的空间方法，其中网络的层是通过节点集合的 hierarchical partitioning 来定义的。在同一篇论文中，作者提出了一种谱方法，将卷积的概念扩展到 graph spectra 。

     • 后来，《Deep Convolutional Networks on Graph-Structured Data》将这些技术应用于这样的数据：图并不是立即出现但是必须被推断。

     属于空间类别的 DCNN 与这项工作不同，因为 DCNN 的参数化（parameterization）使模型可以迁移：在一个图上学习的 DCNN 可以应用于另一个图。

   • 概率关系模型：DCNN 也与概率关系模型（probabilistic relational model: PRM）有着密切的联系。概率关系模型是一族 graphical model ，能够代表关系数据的分布（《Probabilistic Graphical Models: Principles and Techniques》）。与概率关系模型相比，DCNN 是确定性的，这使得 DCNN 能够避免指数爆炸（指数爆炸阻碍了概率关系模型的学习和推断）。

     我们的研究结果表明：DCNN的表现优于部分观察的条件随机场（conditional random field: CRF），即半监督学习的 SOTA 概率关系模型。此外，DCNN 以相当低的计算成本提供这种性能。学习DCNN 和部分观测的 CRF 的参数需要数值上最小化一个非凸目标：对于 DCNN 来说是反向传播误差，对于 CRF 来说是负的边际对数似然。

     • 在实践中，部分观测的 CRF 的边际对数似然是使用对比分区函数（contrast-of-partition-function）方法来计算的，这需要运行两次循环的信念传播（belief propagation）：一次是在整个图上，一次是在固定观测标签的情况下。这种算法，以及数值优化中的每个 step ，具有指数级的时间复杂度 $O(|{\mathcal{E}}_t|\times n_t^{C_t})$$O(|\mathcal E_t|\times n_t^{C_t})$，其中 $C_t$$C_t$是 ${\mathcal{G}}_t$$\mathcal G_t$ 中最大团（maximal clique）的大小。

     • 相比之下，DCNN 的学习程序只需要对训练数据中的每个实例进行一次前向传播和反向传播。复杂度由 graph definition matrix $\mathbf{A}$$\mathbf A$ 和 graph design matrix $\mathbf{V}$$\mathbf V$ 之间的矩阵乘法所支配，整体的多项式复杂度为 $O(n_t^2\times d)$$O(n_t^2\times d)$ 。

     其中，$n_t$$n_t$ 为第 $t$$t$ 个图 ${\mathcal{G}}_t$$\mathcal G_t$ 的节点数量，$|{\mathcal{E}}_t|$$|\mathcal E_t|$ 为图 ${\mathcal{G}}_t$$\mathcal G_t$ 的边数量，$d$$d$ 为输入特征维度。

   • 核方法：核方法（kernel method）定义了节点之间（即 kernel on graph ）或图之间（即 graph kernel ）的相似性度量，这些相似性可以作为通过核技巧（kernel trick）进行预测的基础。graph kernel 的性能可以通过将图分解为子结构，将这些子结构视为句子中的一个词，并拟合一个 word-embedding 模型来获得矢量化来提高。

     DCNN 与kernel on graph 的 exponential diffusion 族有联系。exponential diffusion graph kernel ${\mathbf{K}}_{\text{ED}}$$\mathbf K_\text{ED}$ 是一个矩阵幂级数的和：

     $${\mathbf{K}}_{\text{ED}}=\sum _{j=0}^{\mathrm{\infty }}\frac{{\alpha }^j{\mathbf{A}}^j}{j!}=\exp (\alpha \mathbf{A})$$

     ${\mathbf{Z}}_t=f({\mathbf{W}}^{(c)}\odot \left({\mathbf{P}}_t^{(\ast )}{\mathbf{X}}_t\right))$$\mathbf Z_t = f\left(\mathbf W^{(c)}\odot\left(\mathbf P_t^{(*)}\mathbf X_t\right)\right)$中给出的 diffusion-convolution activation 也是由幂级数构造的。然而，它和 ${\mathbf{K}}_{\text{ED}}$$\mathbf K_\text{ED}$ 有几个重要的区别：

     • 首先，${\mathbf{Z}}_t$$\mathbf Z_t$ 中的权重是通过反向传播学习的，而 kernel representation 不是从数据中学习的。

     • 其次，diffusion-convolution representation是由节点特征和图结构来建立的，而 exponential diffusion kernel 则仅由图结构来建立。

     • 最后，这两种 representation 有不同的维度： ${\mathbf{K}}_{\text{ED}}$$\mathbf K_\text{ED}$ 是一个$n_t\times n_t$$n_t\times n_t$ 的 kernel matrix ，而 ${\mathbf{Z}}_t$$\mathbf Z_t$ 是一个 $n_t\times K\times d$$n_t\times K\times d$ 的张量，不符合 kernel 的定义。其中 $K$$K$ 为最大的 K-hop 邻域。

1.1 模型

1. DCNN 模型建立在扩散核（diffusion kernel）的思想上：基于两个节点之间的所有路径来衡量两个节点的邻近关系，其中路径越短权重越高。

   术语 “扩散卷积” 表明网络的三个思想：特征学习（feature learning）、参数共享、不变性。

   • DCNN 的核心是抽取图结构数据的特征。

   • DCNN 也用到参数共享，其中共享是发生在扩散搜索深度上（diffusion search depth），而不是CNN 的网格位置上。

   • DCNN 关于节点索引不变，即两个同构输入图的扩散卷积的 representation 将是相同的。

   和CNN 不同，DCNN 没有池化操作。

2. 考虑我们有 $T$$T$ 个图 $\mathbb{G}=\{{\mathcal{G}}_t{\}}_{t=1}^T$$\mathbb G=\{\mathcal G_t\}_{t=1}^T$，第 $t$$t$ 个图为 ${\mathcal{G}}_t=({\mathcal{V}}_t,{\mathcal{E}}_t)$$\mathcal G_t=(\mathcal V_t,\mathcal E_t)$ ，它可以是有向图也可以是无向图、可以是带权重也可以是不带权重的图。其中：

   • ${\mathcal{V}}_t=\{v_{t,1},\cdots ,v_{t,n_t}\}$$\mathcal V_t=\{v_{t,1},\cdots,v_{t,n_t}\}$ 为第 $t$$t$ 个图的 $n_t$$n_t$ 个节点集合，${\mathcal{E}}_t$$\mathcal E_t$ 为第 $t$$t$ 个图的边集合。

   • ${\mathbf{A}}_t\in {\mathbb{R}}^{n_t\times n_t}$$\mathbf A_t\in \mathbb R^{n_t\times n_t}$ 为第 $t$$t$ 个图的邻接矩阵； ${\mathbf{D}}_t=\text{diag}(D_{t,i})$$\mathbf D_t=\text{diag}(D_{t,i})$ 为对应的 degree 矩阵，其中 $D_{t,i}=\sum _j{A}_{t,i,j}$$D_{t,i} = \sum_{j}A_{t,i,j}$ 。

   • ${\mathbf{P}}_t={\mathbf{D}}_t^{-1}{\mathbf{A}}_t$$\mathbf P_t=\mathbf D_t^{-1}\mathbf A_t$ 为转移概率矩阵，$P_{t,i,j}$$P_{t,i,j}$ 表示在第 $t$$t$ 个图中节点 $v_{t,i}$$v_{t,i}$ 经过一步转移到节点 $v_{t,j}$$v_{t,j}$ 的概率。

   • 节点 $v_{t,i}\in {\mathcal{V}}_t$$v_{t,i}\in \mathcal V_t$ 关联一个输入特征向量 ${\overrightarrow{\mathbf{x}}}_{t,i}\in {\mathbb{R}}^d$$\mathbf{\vec x}_{t,i}\in \mathbb R^{d}$ 。第 $t$$t$ 个图的所有节点的输入特征向量构成输入特征矩阵 ${\mathbf{X}}_t\in {\mathbb{R}}^{n_t\times d}$$\mathbf X_t\in \mathbb R^{n_t\times d}$ 。

   • 对于节点分类任务，每个节点 $v_{t,i}$$v_{t,i}$ 关联一个标签 $y_{t,i}$$y_{t,i}$ ；对于图分类任务，每个图 ${\mathcal{G}}_t$$\mathcal G_t$ 关联一个标签 $y_t$$y_t$ 。

3. 定义 $K$$K$ 阶转移概率矩阵为 ${\mathbf{P}}_t^{(K)}\in {\mathbb{R}}^{n_t\times n_t}$$\mathbf P_t^{(K)}\in \mathbb R^{n_t\times n_t}$ ，它就是 ${\mathbf{P}}_t$$\mathbf P_t$ 的 $K$$K$ 次幂：

   $${\mathbf{P}}_t^{(K)}=\underset{K}{\underbrace{{\mathbf{P}}_t\cdots {\mathbf{P}}_t}}$$

   ${\mathbf{P}}_t^{(K)}$$\mathbf P_t^{(K)}$ 的元素 $P_{t,i,j}^{(K)}$$P_{t,i,j}^{(K)}$ 表示节点 $v_{t,i}$$v_{t,i}$ 经过 $K$$K$ 步随机游走到达节点 $v_{t,j}$$v_{t,j}$ 的概率。

   令 ${\mathbf{P}}_t^{(\ast )}\in {\mathbb{R}}^{n_t\times K\times n_t}$$\mathbf P_t^{(*)}\in \mathbb R^{n_t\times K\times n_t}$ 包含从 $1\cdots K$$1\cdots K$ 阶的转移概率矩阵，其中：$P_{t,i,k,j}^{(\ast )}=P_{t,i,j}^{(k)}$$P^{(*)}_{t,i,k,j}=P^{(k)}_{t,i,j}$ 。${\mathbf{P}}_t^{(\ast )}$$\mathbf P_t^{(*)}$ 包含所有从节点 $v_{t,i}$$v_{t,i}$ 到节点 $v_{t,j}$$v_{t,j}$ 的、不超过 $K$$K$ 步的随机游走概率。

   定义扩散卷积为：

   $$Z_{t,i,k,s}=f(W_{k,s}^{(c)}\times \sum _{j=1}^{n_t}{P}_{t,i,k,j}^{(\ast )}{X}_{t,j,s})$$

   其中：$i$$i$ 表示节点 $v_{t,i}$$v_{t,i}$；$j$$j$ 表示节点 $v_{t,j}$$v_{t,j}$ ；$k$$k$ 表示 k-hop；$s$$s$ 表示特征维度。

   因此节点 $v_{t,i}$$v_{t,i}$ 得到的 representation 是对图 ${\mathcal{G}}_t$$\mathcal G_t$ 中所有节点、所有维度上加权和得到，加权的权重由两部分组成：

   • 节点之间的转移概率 $P_{t,i,j}^{(k)}$$P^{(k)}_{t,i,j}$ ，它刻画了两个节点之间路径的重要性。

   • 指定维度、指定路径长度的权重 $W_{k,s}^{(c)}$$W^{(c)}_{k,s}$ ，它在相同维度且相同路径长度的所有位置上共享，即在扩散搜索深度上共享。

   以张量形式表示为：

   $${\mathbf{Z}}_t=f({\mathbf{W}}^{(c)}\odot \left({\mathbf{P}}_t^{(\ast )}{\mathbf{X}}_t\right))$$

   其中：

   • ${\mathbf{W}}^{(c)}\in {\mathbb{R}}^{K\times d}$$\mathbf W^{(c)}\in \mathbb R^{K\times d}$ 为待学习的参数矩阵。

   • $\odot$$\odot$ 为逐元素的乘积。

   • ${\mathbf{Z}}_t\in {\mathbb{R}}^{n_t\times K\times d}$$\mathbf Z_t\in \mathbb R^{n_t\times K\times d}$ 为学到的节点 representation 张量。

   可以看到，模型只有 $O(K\times d)$$O(K\times d)$ 个参数，与输入图的规模无关。并且学到的参数可以迁移：在一个图上学到的 DCNN 可以应用到另一个图。

   这里的核心是 ${\mathbf{W}}^{(c)}\in {\mathbb{R}}^{K\times d}$$\mathbf W^{(c)}\in \mathbb R^{K\times d}$ ，它定义了指定路径深度、指定维度的权重。而节点的聚合权重是由 $k$$k$ 阶转移概率矩阵来决定。

4. DCNN 可以用于节点分类或者图分类。

   • 节点分类：一旦得到 ${\mathbf{Z}}_t$$\mathbf Z_t$，则我们可以后续接 dense 层和 softmax 输出层来进行节点分类。

   • 图分类：如果将图 ${\mathcal{G}}_t$$\mathcal G_t$ 中所有节点的激活值取平均，则得到 graph-level 的 representation：

     $${\mathbf{R}}_t=f({\mathbf{W}}^{(c)}\odot \left(\frac{{\overrightarrow{\mathbf{1}}}^{\mathrm{\top }}{\mathbf{P}}_t^{(\ast )}{\mathbf{X}}_t}{n_t}\right))$$

     其中： ${\overrightarrow{\mathbf{1}}}^{\mathrm{\top }}\in {\mathbb{R}}^{1\times n_t}$$\mathbf{\vec 1}^\top\in \mathbb R^{1\times n_t}$ 为全 1 的行向量；${\mathbf{R}}_t\in {\mathbb{R}}^{K\times d}$$\mathbf R_t\in \mathbb R^{ K\times d }$ 为图 ${\mathcal{G}}_t$$\mathcal G_t$ 的 representation 张量。

     一旦得到 ${\mathbf{R}}_t$$\mathbf R_t$，则我们可以后续接 dense 层和 softmax 输出层来进行图分类。

   注意：${\mathbf{Z}}_t,{\mathbf{R}}_t$$\mathbf Z_t,\mathbf R_t$ 给出了 $K$$K$ 个 hop 的 representation，在接入 dense 层之前可以把这 $K$$K$ 个 representation 拼接或者相加从而得到 final representation 。

5. 对于没有节点特征的图，可以人工构造节点特征：

   • 可以为每个节点构造一个取值为 1.0 的 bias feature。

   • 可以使用节点的结构统计信息，如pagerank 值、节点degree 等。

6. DCNN 局限性：

   • 可扩展性（scalability）：DCNN 被实现为对稠密张量的一系列运算。存储 ${\mathbf{P}}^{(\ast )}$$\mathbf P^{(*)}$ 需要 $O(n_t^{2}K)$$O(n_t^2K)$ 的内存，对于较大的图（如百万级甚至更大的图）可能会导致 out-of-memory: OOM错误。

     可以通过随机游走来近似 $k$$k$ 阶转移概率矩阵从而降低计算复杂度和内存需求。

   • 局部性（locality）：DCNN 旨在捕获图结构数据中的局部行为。我们是从每个节点开始的、最高 K 阶的扩散过程来构建representation，因此可能无法对长程依赖或者其它非局部行为进行编码。

7. DCNN 的训练：通过 mini-batch 随机梯度下降来学习。

8. 可以证明：如果两个图 ${\mathcal{G}}_1,{\mathcal{G}}_2$$\mathcal G_1,\mathcal G_2$ 是同构的，则它们的 diffusion-convolutional representation 是相同的；如果两个图 ${\mathcal{G}}_1,{\mathcal{G}}_2$$\mathcal G_1,\mathcal G_2$ 是非同构的，则它们的 diffusion-convolutional representation 是不同的。

   证明见原始论文。

1.2 实验

1. 实验配置：

   • 使用 AdaGrad 算法进行梯度提升，学习率为 0.05 。

   • 从均值为0、方差为 0.01 的正态分布随机采样来初始化所有权重。

   • 选择双曲正切 tanh 函数作为非线性激活函数 $f(\cdot )$$f(\cdot)$ 。

   • 选择多分类 hinge loss 作为损失函数。假设一共 $C$$C$ 个类别，样本 $i$$i$ 的真实类别为 $y_i$$y_i$ ，模型预测为各类别的概率为 ${\overrightarrow{\mathbf{p}}}_i\in {\mathbb{R}}^C$$\mathbf{\vec p}_i\in \mathbb R^C$ 。则样本 $i$$i$ 的损失为：

     $$\begin{array}{c}{\mathcal{L}}_i=\sum _{c\ne y_i,1\le c\le C}\{\begin{array}{ll}0,& \text{if }(p_{y_i}-p_c)\ge ϵ\\ ϵ-(p_{y_i}-p_c),& \text{if }(p_{y_i}-p_c)<ϵ\end{array}=\sum _{c\ne y_i,1\le c\le C}max(0,ϵ-(p_{y_i}-p_c))\end{array}$$

     其中 $ϵ>0$$\epsilon\gt0$ 为间隔阈值。

1.2.1 节点分类

1. 数据集：Cora,Pubmed 论文引用数据集，每个节点代表一篇论文，边代表论文之间的引用关系，标签为论文的主题subject 。这里我们将引文网络视为无向图。

   • Cora 数据集包含 2708 篇论文、5429 条边。每篇论文都分配一个标签，标签来自 7 个可能的机器学习主题。每篇论文都由一个向量表示，向量的每一位对应于是否存在从词典中抽取的 1433 个术语是否存在。

   • Pubmed 数据集包含关于糖尿病的 19717 篇论文、44338 条边。论文被分配到三个类别之一。每篇论文都由一个 TFIDF 向量来表示，其中词典大小为 500 （即论文的特征向量维度为 500）。

2. 这里集合 $\mathbb{G}$$\mathbb G$ 由单个输入图 $\mathcal{G}$$\mathcal G$ 组成，输入图的节点随机划分为训练集、验证集、测试集，每个集合具有相同数量的节点。在训练期间，模型可以看到所有节点的特征、所有边、以及训练集和验证集的标签。

   我们报告了测试集分类准确率以及 micro-F1 和 macro-F1 ，每个指标为多次实验计算得到的均值。

   我们还提供了 CORA 和 Pubmed 数据集的 learning curve，其中验证集和测试集分别包含 10% 的节点，训练集包含剩余节点的 10% ~ 100% 。

3. baseline 方法：

   • l1logistic 和 l2logistic：分别代表 L1 正则化的逻辑回归、L2 正则化的逻辑回归。逻辑回归模型的输入仅仅是节点的特征（并未使用图结构），并使用验证集对正则化参数进行调优。

   • KED 和 KLED：分别代表图上的 exponential diffusion kernel 和 Laplacian exponential diffusion kernel 。这些 kernel model 将图结构作为输入（并未使用节点特征）。

   • CRF-LBP：表示使用循环信念传播（loopy belief propagation: LBP）进行推断的、部分观测（partially-observed）的条件随机场。该模型的结果来自前人论文的实验结果。

4. 下表给出了实验结果，可以看到：DCNN （K=2 ）提供了最佳性能。

   

   • 下图的 (a),(b) 给出了learning curve，可以看到：在 Cora 数据集上，无论可用的训练数据量如何，DCNN 通常都优于baseline 方法。

   • 图(c) 给出 hop 数量的影响。可以看到：随着 hop 数从 0-hop 逐渐增加的过程中，性能先增加然后稳定，在 3-hop 达到收敛。

     

1.2.2 图分类

1. 数据集：我们采用 NCI1、NCI109、MUTAG、PTC、ENZYMES 等标准的图分类数据集。

   • NCI1、NCI109 数据集由代表化合物的 4100 和 4127 个图组成，每个图都标有它是否具有抑制一组人类肿瘤细胞系生长的能力。图中每个节点分类有 37 个（对于 NCI1 ）或 38 个（对于 NCI109） 可能的标记之一。

   • MUTAG 数据集包含 188 个硝基化合物，被标记为芳族或非芳族化合物。节点包含7 个特征。

   • PTC 包含 344 个化合物，被标记为是否对于大鼠致癌。节点包含 19 个特征。

   • ENZYMES 包含 600 个蛋白质的图，每个节点包含3 个特征。

   输入的图集合随机拆分为训练集、验证集、测试集，每个集合包含数量相等的图，我们报告测试集的准确率、micro-F1 和 macro-F1 。每个指标为多次实验计算得到的均值。

2. baseline 方法：

   • l1logistic 和 l2logistic：分别代表 L1 正则化的逻辑回归、L2 正则化的逻辑回归，它们仅利用节点特征。

   • deepwl ：表示 Weisfeiler-Lehman (WL) subtree deep graph kernel ，它仅利用图结构。

3. 下表给出了实验结果，可以看到：和节点分类实验相反，没有明确的最佳模型在所有数据集、所有指标上最优。

   

   我们还提供了 MUTAG（图 (a)）和 ENZYMES（图 (b)） 数据集的learning curve ，其中验证集和测试集都分别包含 10% 的图、训练集包含剩余图的 10% ~ 100% 。从下图 (c) 可以看到：扩大hop 数量并没有明显的好处。

   

   这些结果表明：尽管扩散卷积可以得到节点的有效表示，但是它们在 summarize 整个图的representation 方面做得很差。可以寻找一种方法来更有效地聚合节点来改善graph-level 的 representation，这留待以后工作。